#include <cstring>
#include <iostream>
#include <vector>

/**
 * NowCoder KY107: Shortest Path
 */

struct BigInt {
    uint32_t bits[16];

    BigInt() { std::memset(bits, 0, sizeof(bits)); }

    void set(int pos) {
        int i = pos / 32, j = pos % 32;
        bits[i] |= 1 << j;
    }

    void clear(int pos) {
        int i = pos / 32, j = pos % 32;
        bits[i] &= ~(1 << j);
    }

    int mod() const {
        uint64_t rem = 0;
        for (int i = 15; i >= 0; i--) {
            uint64_t val = (rem << 32) + bits[i];
            rem = val % 100000;
        }
        return int(rem);
    }
};

struct Edge {
    int to;
    int distExp;

    Edge(int to, int distExp) : to(to), distExp(distExp) {}
};

struct Vertex;

std::vector<Vertex> vertices;

struct Vertex {
    int index, root;
    std::vector<Edge> edges;
    int modDist;

    Vertex(int idx) : index(idx), root(idx), modDist(-1) {}

    int find() {
        if (root != index) root = vertices[root].find();
        return root;
    }

    void Union(int other) {
        int r1 = find();
        int r2 = vertices[other].find();
        vertices[r2].root = r1;
    }
};

void search(int idx, BigInt &dist) {
    Vertex &vert = vertices[idx];
    for (int i = 0; i < vert.edges.size(); i++) {
        Edge &edge = vert.edges[i];
        if (vertices[edge.to].modDist != -1) continue;
        dist.set(edge.distExp);
        vertices[edge.to].modDist = dist.mod();
        search(edge.to, dist);
        dist.clear(edge.distExp);
    }
}

int main() {
    // Add edges to graph to form minimal spanning tree
    int nVerts, nEdges;
    scanf("%d %d", &nVerts, &nEdges);
    for (int i = 0; i < nVerts; i++) vertices.push_back(Vertex(i));
    for (int exp = 0; exp < nEdges; exp++) {
        int from, to;
        scanf("%d %d", &from, &to);
        if (vertices[from].find() == vertices[to].find()) continue;
        vertices[from].Union(to);
        vertices[from].edges.push_back(Edge(to, exp));
        vertices[to].edges.push_back(Edge(from, exp));
    }

    // Depth first search the spanning tree to evaluate distances
    vertices[0].modDist = 0;
    BigInt dist;
    search(0, dist);
    for (int i = 1; i < nVerts; i++)
        printf("%d\n", vertices[i].modDist);

    return 0;
}
